package hot;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

public class wuyi {
//    https://leetcode.cn/problems/n-queens/?envType=study-plan-v2&envId=top-100-liked
        static boolean[] right_diagonal;
        static boolean[] left_diagonal;
        static boolean[] Col;
        static int n;
        //记录实时的棋盘
        static char[][] board;
        static List<List<String>> ret=new ArrayList<>();
        public static List<List<String>> solveNQueens(int _n) {
            n=_n;
            right_diagonal=new boolean[2*n];
            left_diagonal=new boolean[2*n];
            board=new char[n][n];
            Col=new boolean[n];
            //先把board全部初始化.
            for(int p=0;p<n;p++){
                for(int q=0;q<n;q++){
                    board[p][q]='.';
                }
            }
            //传递的是行数
            dfs(0);
            return ret;
        }
        public static void dfs(int i){
            if(i==n){
                //将char[][] 转化为LIst<String>
                List<String> tmp= Arrays.stream(board)
                        .map(String::new)
                        .collect(Collectors.toList());
                ret.add(new ArrayList(tmp));
                return;
            }
            for(int col=0;col<n;col++){
                if(!Col[col]&&!right_diagonal[i-col+n]&&!left_diagonal[i+col]){
                    //其实[i,col]就是棋子位置
                    board[i][col]='Q';
                    Col[col]=true;
                    right_diagonal[i-col+n]=true;
                    left_diagonal[i+col]=true;
                    dfs(i+1);
                    //回溯 恢复现场
                    board[i][col]='.';
                    Col[col]=false;
                    right_diagonal[i-col+n]=false;
                    left_diagonal[i+col]=false;
                }
            }
        }

    public static void main(String[] args) {
        List<List<String>> lists = solveNQueens(3);
        System.out.println(lists);
    }
    }

